#include<bits/stdc++.h>
#define int long long
using namespace std;
const double PI=acos(-1.0);
int T,p,n,m;
struct cp{
    double x,y;
    cp operator + (const cp &A) const{
        return (cp){x+A.x,y+A.y};
    }
    cp operator - (const cp &A) const{
        return (cp){x-A.x,y-A.y};
    }
    cp operator * (const cp &A) const{
        return (cp){x*A.x-y*A.y,x*A.y+y*A.x};
    }
}w[8400005],a[8400005];
const int ex_B=8400005;
int ex_rev[ex_B],inv;
vector<int> tree[2005],op,OP;
inline int ksm(int k,int c){
	int a=1,b=k;
	while(c){
		if(c&1) a=(a*b)%p;
		b=(b*b)%p;
		c>>=1; 
	}
	return a;
}
inline cp js(int x,int y){
    if(y<0) y+=x;
    return (cp){cos(PI*2.0*((double)y/(double)x)),sin(PI*2.0*((double)y/(double)x))};
}
inline void add(int &x,int y){
    if((x+y)>=p) x=x+y-p;
    else x+=y;
}
inline void del(int &x,int y){
    if((x-y)<0) x=x-y+p;
    else x-=y;
}
inline void fft(cp *A,int T,int op){
    for(int i=0;i<T;i++) if(i<ex_rev[i]) swap(A[i],A[ex_rev[i]]);
    for(int i=1;i<T;i<<=1){
        w[0]=js(i<<1,0);w[1]=js(i<<1,1*op);
        for(int j=2;j<i;j++) w[j]=w[j-1]*w[1];
        for(int j=0;j<T;j+=(i<<1)){
            for(int g=0;g<i;g++){
                cp x=w[g]*A[j+g+i];
                A[j+g+i]=A[j+g]-x;
                A[j+g]=A[j+g]+x;
            }
        }
    }
}
inline void NTT(vector<int> &A,vector<int> &B,vector<int> &C){
	int T=1;
	while(T<=((int)A.size()+(int)B.size()-2)) T<<=1;
	int len=log2(T);
	for(int i=0;i<T;i++) ex_rev[i]=(ex_rev[i>>1]>>1)|((i&1)<<(len-1));
	for(int i=0;i<T;i++){
		a[i].x=a[i].y=0;
		if(i<(int)A.size()) a[i].x=A[i];
		if(i<(int)B.size()) a[i].y=B[i];
	}
	fft(a,T,1);
    for(int i=0;i<T;i++) a[i]=a[i]*a[i];
    fft(a,T,-1);
    for(int i=0;i<=((int)A.size()+(int)B.size()-2);i++){
        double q=a[i].y/2.0/(double)T;
		int d=(int)(q+0.5);
		C.push_back(d%p);
    }
}
inline void build(int k,int l,int r){
	if(l==r){
		for(int i=0;i<=m;i++) tree[k].push_back(inv);
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);build((k<<1)^1,mid+1,r);
	NTT(tree[k<<1],tree[(k<<1)^1],tree[k]);
}
signed main(){
	cin>>p;
	cin>>T;
	while(T--){
		cin>>n>>m;
		inv=ksm(m+1,p-2);
		op.clear();
		op.push_back((int)1);
		build(1,1,n);
		NTT(op,tree[1],OP);
		int sum=0,ans=0;
		for(int i=(int)OP.size()-1;i>=0;i--){
			add(ans,OP[i]*sum%p);
			add(sum,OP[i]);
		}
		cout<<ans<<"\n";
	}
    return 0;
}